Node *LCA(Node *root, Node *p, Node *q)
{
    if (!root) return NULL;
    if (root == p || root == q) return root;
    Node *L = LCA(root->left, p, q);
    Node *R = LCA(root->right, p, q);
    if (L && R) return root;  // if p and q are on both sides
    return L ? L : R;  // either one of p,q is on one side OR p,q is not in L&R subtrees
}
